1. Field of the Invention
This invention generally relates to the field of image processing systems, and more particularly relates to a system and method for organizing and delivering data for virtual walkthroughs.
2. Description of Related Art
Computer-based user-steered interactive display of a sequence of views of a 3-dimensional scene is potentially of value in a wide range of applications. A key goal of a system for such a xe2x80x9cwalkthroughxe2x80x9d is providing a seemingly-real sequence of images. Reaching this goal for a large scene typically requires great computer power.
Specifically, from a visual model combined with a specification of light sources, viewing position, and viewing angle, a corresponding image can be rendered by the method of ray-tracing or by other well-established algorithms. The data set needed to specify with realistic detail a visual model of a large object, either real or synthetic, such as an industrial building, a ship or a passenger jet may include tens or even hundreds of millions of triangles. For a walkthrough of such scenes and objects to seem real images of the scenes and objects from the walker""s sequence of positions and viewing angles must be rendered at a rate of more than 20 frames per second. Slower rates of frame update yield a jerky, unrealistic appearance. A brute force computer algorithm for constructing a walkthrough might consist of applying one of the well-established rendering algorithms repeatedly to generate each successive view frame. Present rendering algorithms, however, require sufficiently large amounts of computation that when applied on present hardware to produce views of a large model, the required rendering rate of over 20 frames per second can not nearly be reached.
The heavy computational burden of a direct application of ray-tracing to a large visual model occurs in part because this method must examine each triangle in the model to determine whether it is visible from the chosen viewing position and angle. Thus many triangles which do not contribute to the final image may nonetheless be the subject of computation. In addition, for a very detailed model viewed from at least a moderate distance, even triangles which contribute to the final image may each be so small that their contribution is solely to a single pixel. Thus viewed from a moderate distance, a large model may impose the computation of visual details which are not visible in the final image.
A possible means of improving the efficiency of interactively driven viewing of a large object is the method of image based rendering. In place of a triangulated model, image based rendering begins with a collection of images of the object to be viewed. From a finite collection of images, an image from an arbitrarily chosen position and viewing angle is then constructed. For a real object the image collection can be captured from reality. For a synthetic object it can be generated using ray-tracing in an initial preparatory step completed before a walkthrough and having, therefore, no effect on the execution speed the walkthrough itself. Images in the input collection which contribute to the output image are, in effect, close enough to the output image that the determination of the output image entails no calculations corresponding to the elimination of invisible triangle and invisible details encountered in direct ray-tracing.
Recent advances in the method of image based rendering are the subject of U.S. Pat. No. 6,097,394 by M. Levoy and P. Hanrahan, and U.S. Pat. Nos. 6,023,523 and 6,009,188 by M. Cohen, S. Gortler and R. Szeliski. These patents concern primarily isolated objects bounded, for example, by a box and viewed from outside the bounding box. The image collections produced by each of these methods when compressed for convenient transmission and storage turns into either a single or a small number of large coherent units. Applied to the walkthrough of a building with many rooms these methods require the transmission and decompression of a data object of size comparable to the full compressed image collection of the entire building before the viewing of even a single image of a single room in the building. It would be desirable to have a system of image based rendering for walkthroughs which is free of this limitation.
Therefore a need exists to overcome the problems with the prior art as discussed above, and particularly for efficient organization, delivery, and rendering of image data for walkthroughs.
A preferred embodiment of the present invention provides a means of organizing and compressing into segments of limited size the image collection needed for the application of image based rendering to walkthroughs of large objects. For views from a limited range of positions only a corresponding limited segment of data needs to be transmitted, decompressed, and processed. A savings is thereby obtained in the startup time and memory required for execution of a walkthrough.
A method comprises the steps of: covering a region for walkthrough with at least one closed surface, wherein each point in the region is surrounded by at least one closed surface; dividing each of the at least one closed surface into a plurality of patches such that each point of each of the at least one closed surface is contained within at least one patch; providing a representation of a collection of light rays crossing each patch of the plurality of patches in a direction oriented toward the interior of a corresponding closed surface using methods drawn from image based rendering; and for any selected viewing point and viewing angle within a region for walkthrough, constructing a corresponding visible image by methods drawn from image based rendering applied to the representation of the collection of light rays crossing at least one patch of at least one closed surface surrounding the selected viewing point.
According to a preferred embodiment of the present invention, a system comprises: a network; at least one networked computing device; and a computer server, communicatively coupled via the network with the at least one networked computing device, for sending imaging information from the computer server into the network destined for reception by the at least one networked computing device, the computer server comprising: a memory for storing imaging information comprising: a representation of a collection of light rays for each of a plurality of patches constituting at least one closed surface covering a region for walkthrough; and an image server, electrically coupled to the memory, for selecting at least one representation of a collection of light rays crossing at least one patch of the plurality of patches of one of the at least one closed surface of the region for walkthrough, wherein the selected at least one representation of a collection of light rays includes all light rays needed for the image based rendering of a visible image at a selected point and viewing angle.
According to an alternative preferred embodiment, the system further comprises: an image component distributor, electrically coupled to the image server, for sending into the network the selected at least one representation of a collection of light rays destined for reception by, and for rendering the visible image at, the at least one networked computing device.
According to another alternative preferred embodiment, the size of the at least one closed surface is selected to be a small size relative to the region for walkthrough so that the representation of a collection of light rays for each patch of each surface can be kept to within a predetermined size constraint.
According to another alternative preferred embodiment, the at least one networked computing device comprises: a user interface for presenting imaging information to and receiving navigation commands from a user navigating a walkthrough; and a memory for storing a user-selected viewing point and viewing angle within a region for walkthrough, and imaging information comprising: a representation of a collection of light rays for each of a plurality of patches constituting at least one closed surface within a region for walkthrough and surrounding the selected viewing point; and an image client, electrically coupled to the memory, for determining in the course of a walkthrough for which of the at least one closed surface within the region of walkthrough and for which patches of the at least one closed surface within the region for walkthrough a representation of the collection of light rays should be retrieved from the server, wherein the retrieved representations of collections of light rays are selected to insure that the light ray collections present in the memory of the networked computing device includes all light rays needed for the image based rendering of a visible image at a selected point and viewing angle.
According to another alternative preferred embodiment, the networked computing device further comprises: an image component receiver, electrically coupled to the image client, for requesting and receiving from the network the representations of collections of light rays destined for the memory of the networked computing device.
According to another alternative preferred embodiment, the networked computing device further comprises: an image renderer, electrically coupled to the memory, for constructing by the methods of image based rendering from the collections of light rays present in the memory the visible image at the selected point and viewing angle.
Further, according to another alternative preferred embodiment, a computer readable medium contains computer instructions for a system for performing the new and novel operations according to the present invention.